package com.code.nowcoder;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/29 15:47
 *
 * <text style="color:red"> 用例通过率: 65.22% 运行时间: 4001ms 占用内存: 174388KB</>
 */
public class W_The70 {

    ArrayList<Integer>[] node;
    int[] rtn;

    /**
     * 扩散II
     *
     * @param n int整型
     * @param m int整型
     * @param u int整型一维数组
     * @param v int整型一维数组
     * @param x int整型一维数组
     * @param y int整型一维数组
     * @param z int整型一维数组
     * @return int整型一维数组
     */
    public int[] solve(int n, int m, int[] u, int[] v, int[] x, int[] y, int[] z) {
        // write code here
        rtn = new int[n];
        node = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++)
            node[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            node[u[i]].add(v[i]);
            node[v[i]].add(u[i]);
        }
        for (int i = 0; i < x.length; i++) {
            dfs(x[i], -1, 0, y[i], z[i]);
        }
        return rtn;
    }

    /**
     * @param m    需要遍历的索引值
     * @param p    上一个来的节点
     * @param len  现在影响了几个了
     * @param deep 最大影响长度
     * @param n    污染指数
     */
    public void dfs(int m, int p, int len, int deep, int n) {
        rtn[m - 1] += n;
        if (len >= deep) return;
        for (int i = 0; i < node[m].size(); i++) {
            if (node[m].get(i) != p) {
                dfs(node[m].get(i), m, len + 1, deep, n);
            }
        }
    }

    // 5,5,[1,2,3,3],[2,3,4,5],[1,2,3,4,5],[1,1,1,1,1],[1,2,3,4,5]

    // [3,6,14,7,8]

    public static void main(String[] args) {
        W_The70 the70 = new W_The70();
        int[] solve = the70.solve(5, 5, new int[]{1, 2, 3, 3}, new int[]{2, 3, 4, 5}, new int[]{1, 2, 3, 4, 5}, new int[]{1, 1, 1, 1, 1}, new int[]{1, 2, 3, 4, 5});
        System.out.println(Arrays.toString(solve));
    }

}
